Library und Data

library(tidyverse)
Registered S3 methods overwritten by 'dbplyr':
  method         from
  print.tbl_lazy     
  print.tbl_sql      
-- Attaching packages ------------------------------------------------------------------------------- tidyverse 1.3.1 --
v ggplot2 3.3.5     v purrr   0.3.4
v tibble  3.1.4     v dplyr   1.0.7
v tidyr   1.1.3     v stringr 1.4.0
v readr   2.0.1     v forcats 0.5.1
-- Conflicts ---------------------------------------------------------------------------------- tidyverse_conflicts() --
x dplyr::filter() masks stats::filter()
x dplyr::lag()    masks stats::lag()
library(dplyr)
library(data.table)
Warning: Paket ‘data.table’ wurde unter R Version 4.1.2 erstellt
Registered S3 method overwritten by 'data.table':
  method           from
  print.data.table     
data.table 1.14.2 using 4 threads (see ?getDTthreads).  Latest news: r-datatable.com

Attache Paket: ‘data.table’

Die folgenden Objekte sind maskiert von ‘package:dplyr’:

    between, first, last

Das folgende Objekt ist maskiert ‘package:purrr’:

    transpose
library(ggplot2)
library(reshape2)
Warning: Paket ‘reshape2’ wurde unter R Version 4.1.2 erstellt

Attache Paket: ‘reshape2’

Die folgenden Objekte sind maskiert von ‘package:data.table’:

    dcast, melt

Das folgende Objekt ist maskiert ‘package:tidyr’:

    smiths
library(rsample)
Warning: Paket ‘rsample’ wurde unter R Version 4.1.2 erstellt
library(recommenderlab)
Warning: Paket ‘recommenderlab’ wurde unter R Version 4.1.2 erstellt
Lade nötiges Paket: Matrix

Attache Paket: ‘Matrix’

Die folgenden Objekte sind maskiert von ‘package:tidyr’:

    expand, pack, unpack

Lade nötiges Paket: arules
Warning: Paket ‘arules’ wurde unter R Version 4.1.2 erstellt

Attache Paket: ‘arules’

Das folgende Objekt ist maskiert ‘package:dplyr’:

    recode

Die folgenden Objekte sind maskiert von ‘package:base’:

    abbreviate, write

Lade nötiges Paket: proxy
Warning: Paket ‘proxy’ wurde unter R Version 4.1.2 erstellt

Attache Paket: ‘proxy’

Das folgende Objekt ist maskiert ‘package:Matrix’:

    as.matrix

Die folgenden Objekte sind maskiert von ‘package:stats’:

    as.dist, dist

Das folgende Objekt ist maskiert ‘package:base’:

    as.matrix

Lade nötiges Paket: registry
Registered S3 methods overwritten by 'registry':
  method               from 
  print.registry_field proxy
  print.registry_entry proxy
data(MovieLense)
  1. Erzeugung von Film & Nutzerprofilen

1.1 MovieLense Daten einlesen

mx_movielens <- as(MovieLense, "matrix")  # convert realratingmatrix to normal matrix

1.2 Binäre User Liked Items Matrix für alle Nutzer erzeugen.

df_user_liked_items <- as.data.frame(mx_movielens)
df_user_liked_items[df_user_liked_items <= 3] <- 0
df_user_liked_items[df_user_liked_items > 3] <- 1
df_user_liked_items

df_user_liked_items is the binary user-item matrix, where ratings > 3 is converted to 1, the rest to 0.

1.3 Dimension der User Liked Items Matrix prüfen und ausgeben.

dim(df_user_liked_items)
[1]  943 1664

The binary user liked items matrix has 943 users, 1664 films.

1.4 Movie Genre Matrix für alle Filme erzeugen.

mx_movie_genre <- as.data.frame(MovieLenseMeta)
rownames(mx_movie_genre) <- mx_movie_genre$title
mx_movie_genre <- as.matrix(mx_movie_genre[,5:22])   # Movie Genre Matrix
# mx_movie_genre 

1.5 Dimension der Movie Genre Matrix prüfen und ausgeben.

movie genre matrix soll 1664(movie) x 18(genre) Dimension sein.

dim(mx_movie_genre)      
[1] 1664   18

the movie genre matrix has 1664 films, 18 genres

1.6 Anzahl unterschiedlicher Filmprofile bestimmen und visualisieren.

df_genre_movie <- as.data.frame(t(mx_movie_genre))
df_genre_movie$cnt <- rowSums(df_genre_movie == "1")               # new column "cnt": count films of each genre
df_genre_movie <- cbind(genre = rownames(df_genre_movie), df_genre_movie)# new column "genre": genre name copied from rownames
ggplot(df_genre_movie,aes(cnt,genre)) + geom_col() + labs(x= "Anzahl Filme", y="Genre",title="Verteilung der Filme nach Genre Kombination") + 
  theme(plot.title = element_text(hjust = 0.5))

Distribution of films by genres. Drama is the most appeared genre, while fantasy is the least. Around 710 films are drama, only 20 are fantasy.

1.7 User Genre Profil Matrix mit Nutzerprofilen im Genre Vektorraum erzeugen.

df_user_liked_items_0 <- df_user_liked_items 
df_user_liked_items_0[is.na(df_user_liked_items_0)] <- 0
mx_user_genre_bi <- as.matrix(df_user_liked_items_0) %*% mx_movie_genre
 

mx_user_genre_bi: user to genre matrix, each element represents how many times a specific user has liked the genre (rating > 3).

1.8 Dimension der User Genre Profil Matrix prüfen und ausgeben.

Matrix_1 ist 943(user) x 1664(movie) Dimension Matrix_2 ist 1664(movie) x 18(genre) Dimension Matrix_1 x Matrix_2 soll 943(user) x 18(genre) Dimension sein.

dim(mx_user_genre_bi)      
[1] 943  18

The user-genre binary matrix has 943 users, 18 genres.

1.9 Anzahl unterschiedlicher Nutzerprofile bestimmen, wenn Stärke der Genre Kombination (a) vollständig bzw. (b) nur binär berücksichtigt wird.

mx_user_movie_0 <- mx_movielens 
mx_user_movie_0[is.na(mx_user_movie_0)] <- 0
mx_user_genre <- mx_user_movie_0 %*% mx_movie_genre


mx_genre_user <- as.data.frame(t(mx_user_genre))    # a: Stärke Genre Kombination vollständig
mx_genre_user$summe <- rowSums(mx_genre_user)               # new column "summe": summe user ratings of each genre
mx_genre_user <- cbind(genre = rownames(mx_genre_user), mx_genre_user)# new column "genre": genre name copied from rownames
ggplot(mx_genre_user,aes(summe,genre)) + geom_col() + labs(x= "Anzahl Nutzer Rating", y="Genre",title="vollständig: Verteilung der Nutzer Rating nach Genre Kombination") + 
  theme(plot.title = element_text(hjust = 0.5))

mx_genre_user <- mx_genre_user %>% select(-genre)

mx_genre_user_bi <- as.data.frame(t(mx_user_genre_bi))   # User Genre Profil Matrix binary
mx_genre_user_bi$summe <- rowSums(mx_genre_user_bi)# # new column "summe": summe user ratings of each genre
mx_genre_user_bi<- cbind(genre = rownames(mx_genre_user_bi), mx_genre_user_bi)# new column "genre": genre name copied from rownames
ggplot(mx_genre_user_bi,aes(summe,genre)) + geom_col() + labs(x= "Anzahl Nutzer Rating", y="Genre",title="binär: Verteilung der Nutzer Rating nach Genre Kombination") + 
  theme(plot.title = element_text(hjust = 0.5))

mx_genre_user_bi <- mx_genre_user_bi %>% select(-genre)

Both distributions showed very similiar results: drama is the most liked genre, while documentary is least liked.

2 Ähnlichkeit von Nutzern und Filmen 2.1 Cosinus Ähnlichkeit zwischen User Genre und Movie Genre Matrix berechnen.

calc_cos_similarity_twomtrx <- function(mx_1, mx_2){numerator <- (mx_1 %*% mx_2)
     denominator <- sqrt(sum(mx_1^2))*sqrt(sum(mx_2^2))  
     return(numerator / denominator)} 

cos_sim_user_movie <- calc_cos_similarity_twomtrx(mx_user_genre_bi,t(mx_movie_genre)) 
dim(cos_sim_user_movie) 
[1]  943 1664

cos_sim_user_movie is a 943 x 1664 matrix, with the cosine similarities between user-genre and movie-genre.

2.2 Dimension der Matrix der Cosinus Ähnlichkeiten von Nutzern und Filmen prüfen uns ausgeben.

print(paste("Dimension der Matrix der Cosinus Ähnlichkeiten von Nutzern und Filmen sind ",dim(cos_sim_user_movie)[1],"x",dim(cos_sim_user_movie)[2]))
[1] "Dimension der Matrix der Cosinus Ähnlichkeiten von Nutzern und Filmen sind  943 x 1664"

2.3 5 Zahlen Statistik für Matrix der Cosinus Ähnlichkeiten prüfen uns ausgeben.

quantile(cos_sim_user_movie)
          0%          25%          50%          75%         100% 
0.000000e+00 5.261188e-05 1.473133e-04 3.367160e-04 4.535144e-03 

2.4 Cosinus Ähnlichkeiten von Nutzern und Filmen mit Dichteplot visualisieren.

df_24 <- (as.data.frame(cos_sim_user_movie)) # transpose of the cosine similarity as data frame
rownames(df_24) <- c(paste0("user_", 1:943)) # rename the rownames as: user1, user2,...user943
df_24_melt <- reshape2::melt(t(df_24))

p <- ggplot(aes(x=value, colour=Var2), data=df_24_melt)
p + geom_density() + theme(legend.position = "none") + 
  labs(x= "Cosinus Ähnlichkeit", y="Density",title="Verteilung der Cosinus Ähnlichkeiten von Nutzern und Filmen") + 
  theme(plot.title = element_text(hjust = 0.5))

From the density plot above we could see that distibutions of all users are right-skewed with very long tails in some user cases. The peaks in the plot where there is the highest concentration at points, is around 0.0001. (Each color in the plot represents one user.)

2.5 Cosinus Ähnlichkeiten von Nutzern und Filmen mit Dichteplot für Nutzer “241”, “414”, “477”, “526”, “640” und “710”

df_25 <- df_24[c(241,414,477,526,640,710),]
df_25_melt <- reshape2::melt(t(df_25))

p <- ggplot(aes(x=value, colour=Var2), data=df_25_melt)
p + geom_density() +
  labs(x= "Cosinus Ähnlichkeit", y="Density",title="Verteilung der Cosinus Ähnlichkeiten von Nutzern und Filmen") + 
  theme(plot.title = element_text(hjust = 0.5))

The density plot with specific 6 users. The peak cosine similarities are between 0.7e-4 and 3e-4.

3 Empfehlbare Filme 3.1 Bewertete Filme maskieren, d.h. “Negativabzug” der User-Items Matrix erzeugen, um anschliessend Empfehlungen herzuleiten.

# generate matrix Negativabzug: the Ratings -> 0, the NAs -> 1
neg_abzug <- as.data.frame(mx_movielens)
neg_abzug[!is.na(neg_abzug)] <- 0
neg_abzug[is.na(neg_abzug)] <- 1
neg_abzug

3.2 Zeilensumme des “Negativabzuges” der User-Items Matrix für die User “5”, “25”, “50” und “150”

neg_abzug_5 <- neg_abzug[5,]
neg_abzug_25 <- neg_abzug[25,]
neg_abzug_50 <- neg_abzug[50,]
neg_abzug_150 <- neg_abzug[150,]

3.3 5-Zahlen Statistik der Zeilensumme des “Negativabzuges” der User-Items Matrix bestimmen.

neg_abzug_cnt <- rowSums(neg_abzug)
quantile(neg_abzug_cnt)
    0%    25%    50%    75%   100% 
 929.0 1516.5 1600.0 1632.0 1645.0 

4 Top-N Empfehlungen 4.1 Matrix für Bewertung aller Filme durch element-weise Multiplikation der Matrix der Cosinus-Ähnlichkeiten von Nutzern und Filmen und “Negativabzug” der User User-Items Matrix erzeugen.

# matrix with ratings of all films: elementwise multiplication of the cosine-similarity matrix and the "negativabzug" matrix
mx_ratings_all_movie <- cos_sim_user_movie*neg_abzug
mx_ratings_all_movie

4.2 Dimension der Matrix für die Bewertung aller Filme prüfen.

dim(mx_ratings_all_movie)
[1]  943 1664

The dimension 943 users x 1664 movies is same as the cosine similiarity user-movie matrix and the negative abzug matrix.

4.3 Top-20 Listen pro Nutzer extrahieren.

# generate the function to extract top N recommendations for each user
get_topn_rocos <- function(matrix,n){
    dim1 = dim(matrix)[1]
    dim2 = dim(matrix)[2]
    matrix_melt <- reshape2::melt(t(matrix)) %>% rename(UserID = Var2, movie = Var1, cos_sim = value)
    Top <- matrix_melt  %>% arrange(UserID,desc(cos_sim)) %>% mutate(rank = rep(1:dim2,dim1)) %>% filter(rank <= n) %>% reshape2::dcast(UserID ~ rank, value.var = "movie")
    return(Top)}

# Top-20 list for each user
top_20_list <- get_topn_rocos(mx_ratings_all_movie,20)
top_20_list

4.4 Länge der Top-20 Listen pro Nutzer prüfen.

top_20_list_new <- top_20_list %>% select(-UserID) 
top_20_list_new$cnt <- rowSums(!is.na(top_20_list_new)) # count the not NA elements each row

five_number <- summary(top_20_list_new$cnt)[-4] # five number of statistics
five_number
   Min. 1st Qu.  Median 3rd Qu.    Max. 
     20      20      20      20      20 

The 5 numbers Statistics of the recommendation numbers for per user all are 20. This means the length of Top-20 lists for each user are all exactly 20.

4.5 Verteilung der minimalen Ähnlichkeit für Top-N Listen für N = 10, 20, 50 und 100 für alle Nutzer visuell vergleichen.

# generate the function to extract top N minimal similarities for each user
analyze_topn_recos <- function(matrix,n,bins){
    dim1 = dim(matrix)[1]
    dim2 = dim(matrix)[2]
    matrix_melt <- reshape2::melt(t(matrix)) %>% rename(UserID = Var2, movie = Var1, cos_sim = value)
    Top_min <- matrix_melt  %>% arrange(UserID,desc(cos_sim)) %>% mutate(rank = rep(1:dim2,dim1)) %>% filter(rank == n) #filter the minimum of the top-n per user
    c <- ggplot(Top_min,aes(cos_sim)) + geom_histogram(bins = bins) + labs(x= "minimum cosine similarity", y="count",title=paste("Distribution of minimum cosine similarities of Top",n, "lists per user")) + 
  theme(plot.title = element_text(hjust = 0.5))
    return(c)}


par(mfrow=c(2,2))
analyze_topn_recos(mx_ratings_all_movie,10,100)

analyze_topn_recos(mx_ratings_all_movie,20,100)

analyze_topn_recos(mx_ratings_all_movie,50,100)

analyze_topn_recos(mx_ratings_all_movie,100,100)

The minimium cosine similarity of different Top-N lists showed very similar right skewed distibution, with the mode at around 0.0002 frequency between 60 and 80. One difference is, as the N value increases, the maximum bin is smaller, for example, the maximum at top-10 is around 0.0037, while the maximum at top-100 is about 0.0028.

4.6 Top-20 Empfehlungen für Nutzer “5”, “25”, “50” und “150” visuell evaluieren. Funktion create_cleveland_plot() zum visuellen Vergleich von Top N Empfehlungen und Nutzerprofil pro User implementieren, indem Empfehlungen und Nutzerprofil im 19 dimensionalen Genre Raum verglichen werden. Die Funktion create_cleveland_plot() verwendet idealerweise die Funktion get_topn_recos()

Implement create_cleveland_plot() function to visually compare top N recommendations and user profile per user by comparing recommendations and user profile in 19 dimensional genre space. The create_cleveland_plot() function ideally uses the get_topn_recos() function


create_cleverland_plot <- function(mx,i,n){  # mx:input data; i: the ith user; n: number of top-N recommender
  # top-N recommendation lists
  top_n <- as.data.frame(t(get_topn_rocos(mx[i,],n))) %>% slice(2:(n+1)) 
  df_movie_genre <- as.data.frame(mx_movie_genre) 
  nr_genre <- dim(mx_movie_genre)[2]
  df_movie_genre$movie_name <- rownames(df_movie_genre)
  top_n_movie_genre <- left_join(top_n,df_movie_genre,by=c("V1"="movie_name"))%>%select(-V1)
  top_n_movie_genre <- colSums(top_n_movie_genre,na.rm=TRUE,dims=1)
  
  # user profile
  rb <- rbind(top_n_movie_genre,mx_user_genre[i,])
  rownames(rb) <- c("Top_n","user_profile") 
  rb <- as.data.frame(t(rb)) %>% arrange(desc(Top_n))
  rb$genre <- rownames(rb) 
  rb.long <- pivot_longer(rb,cols=c(Top_n,user_profile),names_to="type",values_to="count") %>% arrange(desc(count))

  c <- ggplot(rb.long, aes(count, fct_inorder(genre))) +
        geom_line(aes(group = genre)) +
        geom_point(aes(color = type)) + 
        labs(x="count", y="genre",title= paste("User ",i,": Top - ", n, " recommendations VS user profile ") )+ 
        theme(plot.title = element_text(hjust = 0.5)) 
  return(c)
}


par(mfrow=c(2,2))
create_cleverland_plot(mx_ratings_all_movie,5,20)

create_cleverland_plot(mx_ratings_all_movie,25,20)

create_cleverland_plot(mx_ratings_all_movie,50,20)

create_cleverland_plot(mx_ratings_all_movie,150,20)

The Top-20 recommendations show very similiar trend as the user profile.

4.7 Für Nutzer “133” und “555” Profil mit Top-N Empfehlungen für N = 20, 30, 40, 50 analysieren, visualisieren und diskutieren.

par(mfrow=c(4,2))
create_cleverland_plot(mx_ratings_all_movie,133,20)

create_cleverland_plot(mx_ratings_all_movie,133,30)

create_cleverland_plot(mx_ratings_all_movie,133,40)

create_cleverland_plot(mx_ratings_all_movie,133,50)

create_cleverland_plot(mx_ratings_all_movie,555,20)

create_cleverland_plot(mx_ratings_all_movie,555,30)

create_cleverland_plot(mx_ratings_all_movie,555,40)

create_cleverland_plot(mx_ratings_all_movie,555,50)

In the two user examples, the user 555 has rated more films than user 133. Comparing to the user 133, the top-n recommendation for user 555 showed not only similiar trend to the user profile, but also stable performance with different n settings (N = 20,30,40,50). This means, the users who has rated more films will get more ideal recommendations.

LS0tDQp0aXRsZTogIk1DMiBjb250ZW50IGJhc2VkIHJlY29tbWVuZGVyIg0Kb3V0cHV0OiBodG1sX25vdGVib29rDQotLS0NCg0KTGlicmFyeSB1bmQgRGF0YQ0KDQpgYGB7cn0NCmxpYnJhcnkodGlkeXZlcnNlKQ0KbGlicmFyeShkcGx5cikNCmxpYnJhcnkoZGF0YS50YWJsZSkNCmxpYnJhcnkoZ2dwbG90MikNCmxpYnJhcnkocmVzaGFwZTIpDQpsaWJyYXJ5KHJzYW1wbGUpDQpsaWJyYXJ5KHJlY29tbWVuZGVybGFiKQ0KZGF0YShNb3ZpZUxlbnNlKQ0KYGBgDQoNCg0KMS4gRXJ6ZXVndW5nIHZvbiBGaWxtICYgTnV0emVycHJvZmlsZW4NCg0KMS4xIE1vdmllTGVuc2UgRGF0ZW4gZWlubGVzZW4NCmBgYHtyfQ0KbXhfbW92aWVsZW5zIDwtIGFzKE1vdmllTGVuc2UsICJtYXRyaXgiKSAgIyBjb252ZXJ0IHJlYWxyYXRpbmdtYXRyaXggdG8gbm9ybWFsIG1hdHJpeA0KYGBgDQoNCg0KMS4yIEJpbsOkcmUgVXNlciBMaWtlZCBJdGVtcyBNYXRyaXggZsO8ciBhbGxlIE51dHplciBlcnpldWdlbi4NCmBgYHtyfQ0KZGZfdXNlcl9saWtlZF9pdGVtcyA8LSBhcy5kYXRhLmZyYW1lKG14X21vdmllbGVucykNCmRmX3VzZXJfbGlrZWRfaXRlbXNbZGZfdXNlcl9saWtlZF9pdGVtcyA8PSAzXSA8LSAwDQpkZl91c2VyX2xpa2VkX2l0ZW1zW2RmX3VzZXJfbGlrZWRfaXRlbXMgPiAzXSA8LSAxDQpkZl91c2VyX2xpa2VkX2l0ZW1zDQpgYGANCiMjIyBkZl91c2VyX2xpa2VkX2l0ZW1zIGlzIHRoZSBiaW5hcnkgdXNlci1pdGVtIG1hdHJpeCwgd2hlcmUgcmF0aW5ncyA+IDMgaXMgY29udmVydGVkIHRvIDEsIHRoZSByZXN0IHRvIDAuIA0KDQoxLjMgRGltZW5zaW9uIGRlciBVc2VyIExpa2VkIEl0ZW1zIE1hdHJpeCBwcsO8ZmVuIHVuZCBhdXNnZWJlbi4NCg0KYGBge3J9DQpkaW0oZGZfdXNlcl9saWtlZF9pdGVtcykNCmBgYA0KIyMjIFRoZSBiaW5hcnkgdXNlciBsaWtlZCBpdGVtcyBtYXRyaXggaGFzIDk0MyB1c2VycywgMTY2NCBmaWxtcy4NCg0KMS40IE1vdmllIEdlbnJlIE1hdHJpeCBmw7xyIGFsbGUgRmlsbWUgZXJ6ZXVnZW4uDQpgYGB7cn0NCm14X21vdmllX2dlbnJlIDwtIGFzLmRhdGEuZnJhbWUoTW92aWVMZW5zZU1ldGEpDQpyb3duYW1lcyhteF9tb3ZpZV9nZW5yZSkgPC0gbXhfbW92aWVfZ2VucmUkdGl0bGUNCm14X21vdmllX2dlbnJlIDwtIGFzLm1hdHJpeChteF9tb3ZpZV9nZW5yZVssNToyMl0pICAgIyBNb3ZpZSBHZW5yZSBNYXRyaXgNCiMgbXhfbW92aWVfZ2VucmUgDQpgYGANCg0KMS41IERpbWVuc2lvbiBkZXIgTW92aWUgR2VucmUgTWF0cml4IHByw7xmZW4gdW5kIGF1c2dlYmVuLg0KDQptb3ZpZSBnZW5yZSBtYXRyaXggc29sbCAxNjY0KG1vdmllKSB4IDE4KGdlbnJlKSBEaW1lbnNpb24gc2Vpbi4NCg0KYGBge3J9DQpkaW0obXhfbW92aWVfZ2VucmUpICAgICAgDQpgYGANCiMjIyB0aGUgbW92aWUgZ2VucmUgbWF0cml4IGhhcyAxNjY0IGZpbG1zLCAxOCBnZW5yZXMNCg0KMS42IEFuemFobCB1bnRlcnNjaGllZGxpY2hlciBGaWxtcHJvZmlsZSBiZXN0aW1tZW4gdW5kIHZpc3VhbGlzaWVyZW4uDQoNCmBgYHtyfQ0KZGZfZ2VucmVfbW92aWUgPC0gYXMuZGF0YS5mcmFtZSh0KG14X21vdmllX2dlbnJlKSkNCmRmX2dlbnJlX21vdmllJGNudCA8LSByb3dTdW1zKGRmX2dlbnJlX21vdmllID09ICIxIikgICAgICAgICAgICAgICAjIG5ldyBjb2x1bW4gImNudCI6IGNvdW50IGZpbG1zIG9mIGVhY2ggZ2VucmUNCmRmX2dlbnJlX21vdmllIDwtIGNiaW5kKGdlbnJlID0gcm93bmFtZXMoZGZfZ2VucmVfbW92aWUpLCBkZl9nZW5yZV9tb3ZpZSkjIG5ldyBjb2x1bW4gImdlbnJlIjogZ2VucmUgbmFtZSBjb3BpZWQgZnJvbSByb3duYW1lcw0KZ2dwbG90KGRmX2dlbnJlX21vdmllLGFlcyhjbnQsZ2VucmUpKSArIGdlb21fY29sKCkgKyBsYWJzKHg9ICJBbnphaGwgRmlsbWUiLCB5PSJHZW5yZSIsdGl0bGU9IlZlcnRlaWx1bmcgZGVyIEZpbG1lIG5hY2ggR2VucmUgS29tYmluYXRpb24iKSArIA0KICB0aGVtZShwbG90LnRpdGxlID0gZWxlbWVudF90ZXh0KGhqdXN0ID0gMC41KSkNCmBgYA0KDQojIyMgRGlzdHJpYnV0aW9uIG9mIGZpbG1zIGJ5IGdlbnJlcy4gRHJhbWEgaXMgdGhlIG1vc3QgYXBwZWFyZWQgZ2VucmUsIHdoaWxlIGZhbnRhc3kgaXMgdGhlIGxlYXN0LiBBcm91bmQgNzEwIGZpbG1zIGFyZSBkcmFtYSwgb25seSAyMCBhcmUgZmFudGFzeS4gDQoNCjEuNyBVc2VyIEdlbnJlIFByb2ZpbCBNYXRyaXggbWl0IE51dHplcnByb2ZpbGVuIGltIEdlbnJlIFZla3RvcnJhdW0gZXJ6ZXVnZW4uDQoNCmBgYHtyfQ0KZGZfdXNlcl9saWtlZF9pdGVtc18wIDwtIGRmX3VzZXJfbGlrZWRfaXRlbXMgDQpkZl91c2VyX2xpa2VkX2l0ZW1zXzBbaXMubmEoZGZfdXNlcl9saWtlZF9pdGVtc18wKV0gPC0gMA0KbXhfdXNlcl9nZW5yZV9iaSA8LSBhcy5tYXRyaXgoZGZfdXNlcl9saWtlZF9pdGVtc18wKSAlKiUgbXhfbW92aWVfZ2VucmUNCiANCmBgYA0KIyMjIG14X3VzZXJfZ2VucmVfYmk6IHVzZXIgdG8gZ2VucmUgbWF0cml4LCBlYWNoIGVsZW1lbnQgcmVwcmVzZW50cyBob3cgbWFueSB0aW1lcyBhIHNwZWNpZmljIHVzZXIgaGFzIGxpa2VkIHRoZSBnZW5yZSAocmF0aW5nID4gMykuIA0KDQoxLjggRGltZW5zaW9uIGRlciBVc2VyIEdlbnJlIFByb2ZpbCBNYXRyaXggcHLDvGZlbiB1bmQgYXVzZ2ViZW4uDQoNCk1hdHJpeF8xIGlzdCA5NDModXNlcikgeCAxNjY0KG1vdmllKSBEaW1lbnNpb24NCk1hdHJpeF8yIGlzdCAxNjY0KG1vdmllKSB4IDE4KGdlbnJlKSBEaW1lbnNpb24NCk1hdHJpeF8xIHggTWF0cml4XzIgc29sbCA5NDModXNlcikgeCAxOChnZW5yZSkgRGltZW5zaW9uIHNlaW4uDQoNCmBgYHtyfQ0KZGltKG14X3VzZXJfZ2VucmVfYmkpICAgICAgDQpgYGANCiMjIyBUaGUgdXNlci1nZW5yZSBiaW5hcnkgbWF0cml4IGhhcyA5NDMgdXNlcnMsIDE4IGdlbnJlcy4NCg0KMS45IEFuemFobCB1bnRlcnNjaGllZGxpY2hlciBOdXR6ZXJwcm9maWxlIGJlc3RpbW1lbiwgd2VubiBTdMOkcmtlIGRlciBHZW5yZSBLb21iaW5hdGlvbiAoYSkgdm9sbHN0w6RuZGlnIGJ6dy4gKGIpIG51ciBiaW7DpHIgYmVyw7xja3NpY2h0aWd0IHdpcmQuDQoNCmBgYHtyfQ0KbXhfdXNlcl9tb3ZpZV8wIDwtIG14X21vdmllbGVucyANCm14X3VzZXJfbW92aWVfMFtpcy5uYShteF91c2VyX21vdmllXzApXSA8LSAwDQpteF91c2VyX2dlbnJlIDwtIG14X3VzZXJfbW92aWVfMCAlKiUgbXhfbW92aWVfZ2VucmUNCg0KDQpteF9nZW5yZV91c2VyIDwtIGFzLmRhdGEuZnJhbWUodChteF91c2VyX2dlbnJlKSkgICAgIyBhOiBTdMOkcmtlIEdlbnJlIEtvbWJpbmF0aW9uIHZvbGxzdMOkbmRpZw0KbXhfZ2VucmVfdXNlciRzdW1tZSA8LSByb3dTdW1zKG14X2dlbnJlX3VzZXIpICAgICAgICAgICAgICAgIyBuZXcgY29sdW1uICJzdW1tZSI6IHN1bW1lIHVzZXIgcmF0aW5ncyBvZiBlYWNoIGdlbnJlDQpteF9nZW5yZV91c2VyIDwtIGNiaW5kKGdlbnJlID0gcm93bmFtZXMobXhfZ2VucmVfdXNlciksIG14X2dlbnJlX3VzZXIpIyBuZXcgY29sdW1uICJnZW5yZSI6IGdlbnJlIG5hbWUgY29waWVkIGZyb20gcm93bmFtZXMNCmdncGxvdChteF9nZW5yZV91c2VyLGFlcyhzdW1tZSxnZW5yZSkpICsgZ2VvbV9jb2woKSArIGxhYnMoeD0gIkFuemFobCBOdXR6ZXIgUmF0aW5nIiwgeT0iR2VucmUiLHRpdGxlPSJ2b2xsc3TDpG5kaWc6IFZlcnRlaWx1bmcgZGVyIE51dHplciBSYXRpbmcgbmFjaCBHZW5yZSBLb21iaW5hdGlvbiIpICsgDQogIHRoZW1lKHBsb3QudGl0bGUgPSBlbGVtZW50X3RleHQoaGp1c3QgPSAwLjUpKQ0KbXhfZ2VucmVfdXNlciA8LSBteF9nZW5yZV91c2VyICU+JSBzZWxlY3QoLWdlbnJlKQ0KYGBgDQoNCmBgYHtyfQ0KDQpteF9nZW5yZV91c2VyX2JpIDwtIGFzLmRhdGEuZnJhbWUodChteF91c2VyX2dlbnJlX2JpKSkgICAjIFVzZXIgR2VucmUgUHJvZmlsIE1hdHJpeCBiaW5hcnkNCm14X2dlbnJlX3VzZXJfYmkkc3VtbWUgPC0gcm93U3VtcyhteF9nZW5yZV91c2VyX2JpKSMgIyBuZXcgY29sdW1uICJzdW1tZSI6IHN1bW1lIHVzZXIgcmF0aW5ncyBvZiBlYWNoIGdlbnJlDQpteF9nZW5yZV91c2VyX2JpPC0gY2JpbmQoZ2VucmUgPSByb3duYW1lcyhteF9nZW5yZV91c2VyX2JpKSwgbXhfZ2VucmVfdXNlcl9iaSkjIG5ldyBjb2x1bW4gImdlbnJlIjogZ2VucmUgbmFtZSBjb3BpZWQgZnJvbSByb3duYW1lcw0KZ2dwbG90KG14X2dlbnJlX3VzZXJfYmksYWVzKHN1bW1lLGdlbnJlKSkgKyBnZW9tX2NvbCgpICsgbGFicyh4PSAiQW56YWhsIE51dHplciBSYXRpbmciLCB5PSJHZW5yZSIsdGl0bGU9ImJpbsOkcjogVmVydGVpbHVuZyBkZXIgTnV0emVyIFJhdGluZyBuYWNoIEdlbnJlIEtvbWJpbmF0aW9uIikgKyANCiAgdGhlbWUocGxvdC50aXRsZSA9IGVsZW1lbnRfdGV4dChoanVzdCA9IDAuNSkpDQpteF9nZW5yZV91c2VyX2JpIDwtIG14X2dlbnJlX3VzZXJfYmkgJT4lIHNlbGVjdCgtZ2VucmUpDQpgYGANCg0KIyMjIEJvdGggZGlzdHJpYnV0aW9ucyBzaG93ZWQgdmVyeSBzaW1pbGlhciByZXN1bHRzOiBkcmFtYSBpcyB0aGUgbW9zdCBsaWtlZCBnZW5yZSwgd2hpbGUgZG9jdW1lbnRhcnkgaXMgbGVhc3QgbGlrZWQuDQoNCjIgw4RobmxpY2hrZWl0IHZvbiBOdXR6ZXJuIHVuZCBGaWxtZW4NCjIuMSBDb3NpbnVzIMOEaG5saWNoa2VpdCB6d2lzY2hlbiBVc2VyIEdlbnJlIHVuZCBNb3ZpZSBHZW5yZSBNYXRyaXggYmVyZWNobmVuLg0KDQpgYGB7cn0NCmNhbGNfY29zX3NpbWlsYXJpdHlfdHdvbXRyeCA8LSBmdW5jdGlvbihteF8xLCBteF8yKXtudW1lcmF0b3IgPC0gKG14XzEgJSolIG14XzIpDQogICAgIGRlbm9taW5hdG9yIDwtIHNxcnQoc3VtKG14XzFeMikpKnNxcnQoc3VtKG14XzJeMikpICANCiAgICAgcmV0dXJuKG51bWVyYXRvciAvIGRlbm9taW5hdG9yKX0gDQoNCmNvc19zaW1fdXNlcl9tb3ZpZSA8LSBjYWxjX2Nvc19zaW1pbGFyaXR5X3R3b210cngobXhfdXNlcl9nZW5yZV9iaSx0KG14X21vdmllX2dlbnJlKSkgDQpkaW0oY29zX3NpbV91c2VyX21vdmllKSANCmBgYA0KIyMjIGNvc19zaW1fdXNlcl9tb3ZpZSBpcyBhIDk0MyB4IDE2NjQgbWF0cml4LCB3aXRoIHRoZSBjb3NpbmUgc2ltaWxhcml0aWVzIGJldHdlZW4gdXNlci1nZW5yZSBhbmQgbW92aWUtZ2VucmUuDQoNCg0KDQoyLjIgRGltZW5zaW9uIGRlciBNYXRyaXggZGVyIENvc2ludXMgw4RobmxpY2hrZWl0ZW4gdm9uIE51dHplcm4gdW5kIEZpbG1lbiBwcsO8ZmVuIHVucyBhdXNnZWJlbi4NCmBgYHtyfQ0KcHJpbnQocGFzdGUoIkRpbWVuc2lvbiBkZXIgTWF0cml4IGRlciBDb3NpbnVzIMOEaG5saWNoa2VpdGVuIHZvbiBOdXR6ZXJuIHVuZCBGaWxtZW4gc2luZCAiLGRpbShjb3Nfc2ltX3VzZXJfbW92aWUpWzFdLCJ4IixkaW0oY29zX3NpbV91c2VyX21vdmllKVsyXSkpDQpgYGANCg0KMi4zIDUgWmFobGVuIFN0YXRpc3RpayBmw7xyIE1hdHJpeCBkZXIgQ29zaW51cyDDhGhubGljaGtlaXRlbiBwcsO8ZmVuIHVucyBhdXNnZWJlbi4NCg0KYGBge3J9DQpxdWFudGlsZShjb3Nfc2ltX3VzZXJfbW92aWUpDQpgYGANCg0KMi40IENvc2ludXMgw4RobmxpY2hrZWl0ZW4gdm9uIE51dHplcm4gdW5kIEZpbG1lbiBtaXQgRGljaHRlcGxvdCB2aXN1YWxpc2llcmVuLg0KDQpgYGB7cn0NCmRmXzI0IDwtIChhcy5kYXRhLmZyYW1lKGNvc19zaW1fdXNlcl9tb3ZpZSkpICMgdHJhbnNwb3NlIG9mIHRoZSBjb3NpbmUgc2ltaWxhcml0eSBhcyBkYXRhIGZyYW1lDQpyb3duYW1lcyhkZl8yNCkgPC0gYyhwYXN0ZTAoInVzZXJfIiwgMTo5NDMpKSAjIHJlbmFtZSB0aGUgcm93bmFtZXMgYXM6IHVzZXIxLCB1c2VyMiwuLi51c2VyOTQzDQpkZl8yNF9tZWx0IDwtIHJlc2hhcGUyOjptZWx0KHQoZGZfMjQpKQ0KDQpwIDwtIGdncGxvdChhZXMoeD12YWx1ZSwgY29sb3VyPVZhcjIpLCBkYXRhPWRmXzI0X21lbHQpDQpwICsgZ2VvbV9kZW5zaXR5KCkgKyB0aGVtZShsZWdlbmQucG9zaXRpb24gPSAibm9uZSIpICsgDQogIGxhYnMoeD0gIkNvc2ludXMgw4RobmxpY2hrZWl0IiwgeT0iRGVuc2l0eSIsdGl0bGU9IlZlcnRlaWx1bmcgZGVyIENvc2ludXMgw4RobmxpY2hrZWl0ZW4gdm9uIE51dHplcm4gdW5kIEZpbG1lbiIpICsgDQogIHRoZW1lKHBsb3QudGl0bGUgPSBlbGVtZW50X3RleHQoaGp1c3QgPSAwLjUpKQ0KYGBgDQojIyMgRnJvbSB0aGUgZGVuc2l0eSBwbG90IGFib3ZlIHdlIGNvdWxkIHNlZSB0aGF0IGRpc3RpYnV0aW9ucyBvZiBhbGwgdXNlcnMgYXJlIHJpZ2h0LXNrZXdlZCB3aXRoIHZlcnkgbG9uZyB0YWlscyBpbiBzb21lIHVzZXIgY2FzZXMuIFRoZSBwZWFrcyBpbiB0aGUgcGxvdCB3aGVyZSB0aGVyZSBpcyB0aGUgaGlnaGVzdCBjb25jZW50cmF0aW9uIGF0IHBvaW50cywgaXMgYXJvdW5kIDAuMDAwMS4gKEVhY2ggY29sb3IgaW4gdGhlIHBsb3QgcmVwcmVzZW50cyBvbmUgdXNlci4pDQoNCjIuNSBDb3NpbnVzIMOEaG5saWNoa2VpdGVuIHZvbiBOdXR6ZXJuIHVuZCBGaWxtZW4gbWl0IERpY2h0ZXBsb3QgZsO8ciBOdXR6ZXIg4oCcMjQx4oCdLCDigJw0MTTigJ0sIOKAnDQ3N+KAnSwg4oCcNTI24oCdLCDigJw2NDDigJ0gdW5kIOKAnDcxMOKAnQ0KDQpgYGB7cn0NCmRmXzI1IDwtIGRmXzI0W2MoMjQxLDQxNCw0NzcsNTI2LDY0MCw3MTApLF0NCmRmXzI1X21lbHQgPC0gcmVzaGFwZTI6Om1lbHQodChkZl8yNSkpDQoNCnAgPC0gZ2dwbG90KGFlcyh4PXZhbHVlLCBjb2xvdXI9VmFyMiksIGRhdGE9ZGZfMjVfbWVsdCkNCnAgKyBnZW9tX2RlbnNpdHkoKSArDQogIGxhYnMoeD0gIkNvc2ludXMgw4RobmxpY2hrZWl0IiwgeT0iRGVuc2l0eSIsdGl0bGU9IlZlcnRlaWx1bmcgZGVyIENvc2ludXMgw4RobmxpY2hrZWl0ZW4gdm9uIE51dHplcm4gdW5kIEZpbG1lbiIpICsgDQogIHRoZW1lKHBsb3QudGl0bGUgPSBlbGVtZW50X3RleHQoaGp1c3QgPSAwLjUpKQ0KYGBgDQojIyMgVGhlIGRlbnNpdHkgcGxvdCB3aXRoIHNwZWNpZmljIDYgdXNlcnMuIFRoZSBwZWFrIGNvc2luZSBzaW1pbGFyaXRpZXMgYXJlIGJldHdlZW4gMC43ZS00IGFuZCAzZS00Lg0KDQoNCjMgRW1wZmVobGJhcmUgRmlsbWUNCjMuMSBCZXdlcnRldGUgRmlsbWUgbWFza2llcmVuLCBkLmguIOKAnE5lZ2F0aXZhYnp1Z+KAnSBkZXIgVXNlci1JdGVtcyBNYXRyaXggZXJ6ZXVnZW4sIHVtIGFuc2NobGllc3NlbmQgRW1wZmVobHVuZ2VuIGhlcnp1bGVpdGVuLg0KDQpgYGB7cn0NCiMgZ2VuZXJhdGUgbWF0cml4IE5lZ2F0aXZhYnp1ZzogdGhlIFJhdGluZ3MgLT4gMCwgdGhlIE5BcyAtPiAxDQpuZWdfYWJ6dWcgPC0gYXMuZGF0YS5mcmFtZShteF9tb3ZpZWxlbnMpDQpuZWdfYWJ6dWdbIWlzLm5hKG5lZ19hYnp1ZyldIDwtIDANCm5lZ19hYnp1Z1tpcy5uYShuZWdfYWJ6dWcpXSA8LSAxDQpuZWdfYWJ6dWcNCmBgYA0KDQozLjIgWmVpbGVuc3VtbWUgZGVzIOKAnE5lZ2F0aXZhYnp1Z2Vz4oCdIGRlciBVc2VyLUl0ZW1zIE1hdHJpeCBmw7xyIGRpZSBVc2VyIOKAnDXigJ0sIOKAnDI14oCdLCDigJw1MOKAnSB1bmQg4oCcMTUw4oCdDQoNCmBgYHtyfQ0KbmVnX2FienVnXzUgPC0gbmVnX2FienVnWzUsXQ0KbmVnX2FienVnXzI1IDwtIG5lZ19hYnp1Z1syNSxdDQpuZWdfYWJ6dWdfNTAgPC0gbmVnX2FienVnWzUwLF0NCm5lZ19hYnp1Z18xNTAgPC0gbmVnX2FienVnWzE1MCxdDQpgYGANCg0KMy4zIDUtWmFobGVuIFN0YXRpc3RpayBkZXIgWmVpbGVuc3VtbWUgZGVzIOKAnE5lZ2F0aXZhYnp1Z2Vz4oCdIGRlciBVc2VyLUl0ZW1zIE1hdHJpeCBiZXN0aW1tZW4uDQoNCmBgYHtyfQ0KbmVnX2FienVnX2NudCA8LSByb3dTdW1zKG5lZ19hYnp1ZykNCnF1YW50aWxlKG5lZ19hYnp1Z19jbnQpDQpgYGANCg0KDQo0IFRvcC1OIEVtcGZlaGx1bmdlbg0KNC4xIE1hdHJpeCBmw7xyIEJld2VydHVuZyBhbGxlciBGaWxtZSBkdXJjaCBlbGVtZW50LXdlaXNlIE11bHRpcGxpa2F0aW9uIGRlciBNYXRyaXggZGVyIENvc2ludXMtw4RobmxpY2hrZWl0ZW4gdm9uIE51dHplcm4gdW5kIEZpbG1lbiB1bmQg4oCcTmVnYXRpdmFienVn4oCdIGRlciBVc2VyIFVzZXItSXRlbXMgTWF0cml4IGVyemV1Z2VuLg0KDQpgYGB7cn0NCiMgbWF0cml4IHdpdGggcmF0aW5ncyBvZiBhbGwgZmlsbXM6IGVsZW1lbnR3aXNlIG11bHRpcGxpY2F0aW9uIG9mIHRoZSBjb3NpbmUtc2ltaWxhcml0eSBtYXRyaXggYW5kIHRoZSAibmVnYXRpdmFienVnIiBtYXRyaXgNCm14X3JhdGluZ3NfYWxsX21vdmllIDwtIGNvc19zaW1fdXNlcl9tb3ZpZSpuZWdfYWJ6dWcNCm14X3JhdGluZ3NfYWxsX21vdmllDQpgYGANCg0KNC4yIERpbWVuc2lvbiBkZXIgTWF0cml4IGbDvHIgZGllIEJld2VydHVuZyBhbGxlciBGaWxtZSBwcsO8ZmVuLg0KYGBge3J9DQpkaW0obXhfcmF0aW5nc19hbGxfbW92aWUpDQpgYGANCiMjIyBUaGUgZGltZW5zaW9uIDk0MyB1c2VycyB4IDE2NjQgbW92aWVzIGlzIHNhbWUgYXMgdGhlIGNvc2luZSBzaW1pbGlhcml0eSB1c2VyLW1vdmllIG1hdHJpeCBhbmQgdGhlIG5lZ2F0aXZlIGFienVnIG1hdHJpeC4NCg0KNC4zIFRvcC0yMCBMaXN0ZW4gcHJvIE51dHplciBleHRyYWhpZXJlbi4NCg0KYGBge3J9DQojIGdlbmVyYXRlIHRoZSBmdW5jdGlvbiB0byBleHRyYWN0IHRvcCBOIHJlY29tbWVuZGF0aW9ucyBmb3IgZWFjaCB1c2VyDQpnZXRfdG9wbl9yb2NvcyA8LSBmdW5jdGlvbihtYXRyaXgsbil7DQogICAgZGltMSA9IGRpbShtYXRyaXgpWzFdDQogICAgZGltMiA9IGRpbShtYXRyaXgpWzJdDQogICAgbWF0cml4X21lbHQgPC0gcmVzaGFwZTI6Om1lbHQodChtYXRyaXgpKSAlPiUgcmVuYW1lKFVzZXJJRCA9IFZhcjIsIG1vdmllID0gVmFyMSwgY29zX3NpbSA9IHZhbHVlKQ0KICAgIFRvcCA8LSBtYXRyaXhfbWVsdCAgJT4lIGFycmFuZ2UoVXNlcklELGRlc2MoY29zX3NpbSkpICU+JSBtdXRhdGUocmFuayA9IHJlcCgxOmRpbTIsZGltMSkpICU+JSBmaWx0ZXIocmFuayA8PSBuKSAlPiUgcmVzaGFwZTI6OmRjYXN0KFVzZXJJRCB+IHJhbmssIHZhbHVlLnZhciA9ICJtb3ZpZSIpDQogICAgcmV0dXJuKFRvcCl9DQoNCiMgVG9wLTIwIGxpc3QgZm9yIGVhY2ggdXNlcg0KdG9wXzIwX2xpc3QgPC0gZ2V0X3RvcG5fcm9jb3MobXhfcmF0aW5nc19hbGxfbW92aWUsMjApDQp0b3BfMjBfbGlzdA0KYGBgDQoNCjQuNCBMw6RuZ2UgZGVyIFRvcC0yMCBMaXN0ZW4gcHJvIE51dHplciBwcsO8ZmVuLg0KDQpgYGB7cn0NCnRvcF8yMF9saXN0X25ldyA8LSB0b3BfMjBfbGlzdCAlPiUgc2VsZWN0KC1Vc2VySUQpIA0KdG9wXzIwX2xpc3RfbmV3JGNudCA8LSByb3dTdW1zKCFpcy5uYSh0b3BfMjBfbGlzdF9uZXcpKSAjIGNvdW50IHRoZSBub3QgTkEgZWxlbWVudHMgZWFjaCByb3cNCg0KZml2ZV9udW1iZXIgPC0gc3VtbWFyeSh0b3BfMjBfbGlzdF9uZXckY250KVstNF0gIyBmaXZlIG51bWJlciBvZiBzdGF0aXN0aWNzDQpmaXZlX251bWJlcg0KYGBgDQojIyMgVGhlIDUgbnVtYmVycyBTdGF0aXN0aWNzIG9mIHRoZSByZWNvbW1lbmRhdGlvbiBudW1iZXJzIGZvciBwZXIgdXNlciBhbGwgYXJlIDIwLiBUaGlzIG1lYW5zIHRoZSBsZW5ndGggb2YgVG9wLTIwIGxpc3RzIGZvciBlYWNoIHVzZXIgYXJlIGFsbCBleGFjdGx5IDIwLg0KDQo0LjUgVmVydGVpbHVuZyBkZXIgbWluaW1hbGVuIMOEaG5saWNoa2VpdCBmw7xyIFRvcC1OIExpc3RlbiBmw7xyIE4gPSAxMCwgMjAsIDUwIHVuZA0KMTAwIGbDvHIgYWxsZSBOdXR6ZXIgdmlzdWVsbCB2ZXJnbGVpY2hlbi4NCg0KYGBge3J9DQojIGdlbmVyYXRlIHRoZSBmdW5jdGlvbiB0byBleHRyYWN0IHRvcCBOIG1pbmltYWwgc2ltaWxhcml0aWVzIGZvciBlYWNoIHVzZXINCmFuYWx5emVfdG9wbl9yZWNvcyA8LSBmdW5jdGlvbihtYXRyaXgsbixiaW5zKXsNCiAgICBkaW0xID0gZGltKG1hdHJpeClbMV0NCiAgICBkaW0yID0gZGltKG1hdHJpeClbMl0NCiAgICBtYXRyaXhfbWVsdCA8LSByZXNoYXBlMjo6bWVsdCh0KG1hdHJpeCkpICU+JSByZW5hbWUoVXNlcklEID0gVmFyMiwgbW92aWUgPSBWYXIxLCBjb3Nfc2ltID0gdmFsdWUpDQogICAgVG9wX21pbiA8LSBtYXRyaXhfbWVsdCAgJT4lIGFycmFuZ2UoVXNlcklELGRlc2MoY29zX3NpbSkpICU+JSBtdXRhdGUocmFuayA9IHJlcCgxOmRpbTIsZGltMSkpICU+JSBmaWx0ZXIocmFuayA9PSBuKSAjZmlsdGVyIHRoZSBtaW5pbXVtIG9mIHRoZSB0b3AtbiBwZXIgdXNlcg0KICAgIGMgPC0gZ2dwbG90KFRvcF9taW4sYWVzKGNvc19zaW0pKSArIGdlb21faGlzdG9ncmFtKGJpbnMgPSBiaW5zKSArIGxhYnMoeD0gIm1pbmltdW0gY29zaW5lIHNpbWlsYXJpdHkiLCB5PSJjb3VudCIsdGl0bGU9cGFzdGUoIkRpc3RyaWJ1dGlvbiBvZiBtaW5pbXVtIGNvc2luZSBzaW1pbGFyaXRpZXMgb2YgVG9wIixuLCAibGlzdHMgcGVyIHVzZXIiKSkgKyANCiAgdGhlbWUocGxvdC50aXRsZSA9IGVsZW1lbnRfdGV4dChoanVzdCA9IDAuNSkpDQogICAgcmV0dXJuKGMpfQ0KDQoNCnBhcihtZnJvdz1jKDIsMikpDQphbmFseXplX3RvcG5fcmVjb3MobXhfcmF0aW5nc19hbGxfbW92aWUsMTAsMTAwKQ0KYW5hbHl6ZV90b3BuX3JlY29zKG14X3JhdGluZ3NfYWxsX21vdmllLDIwLDEwMCkNCmFuYWx5emVfdG9wbl9yZWNvcyhteF9yYXRpbmdzX2FsbF9tb3ZpZSw1MCwxMDApDQphbmFseXplX3RvcG5fcmVjb3MobXhfcmF0aW5nc19hbGxfbW92aWUsMTAwLDEwMCkNCmBgYA0KIyMjIFRoZSBtaW5pbWl1bSBjb3NpbmUgc2ltaWxhcml0eSBvZiBkaWZmZXJlbnQgVG9wLU4gbGlzdHMgc2hvd2VkIHZlcnkgc2ltaWxhciByaWdodCBza2V3ZWQgZGlzdGlidXRpb24sIHdpdGggdGhlIG1vZGUgYXQgYXJvdW5kIDAuMDAwMiBmcmVxdWVuY3kgYmV0d2VlbiA2MCBhbmQgODAuIE9uZSBkaWZmZXJlbmNlIGlzLCBhcyB0aGUgTiB2YWx1ZSBpbmNyZWFzZXMsIHRoZSBtYXhpbXVtIGJpbiBpcyBzbWFsbGVyLCBmb3IgZXhhbXBsZSwgdGhlIG1heGltdW0gYXQgdG9wLTEwIGlzIGFyb3VuZCAwLjAwMzcsIHdoaWxlIHRoZSBtYXhpbXVtIGF0IHRvcC0xMDAgaXMgYWJvdXQgMC4wMDI4Lg0KDQo0LjYgVG9wLTIwIEVtcGZlaGx1bmdlbiBmw7xyIE51dHplciDigJw14oCdLCDigJwyNeKAnSwg4oCcNTDigJ0gdW5kIOKAnDE1MOKAnSB2aXN1ZWxsIGV2YWx1aWVyZW4uDQpGdW5rdGlvbiBjcmVhdGVfY2xldmVsYW5kX3Bsb3QoKSB6dW0gdmlzdWVsbGVuIFZlcmdsZWljaCB2b24gVG9wIE4gRW1wZmVobHVuZ2VuIHVuZCBOdXR6ZXJwcm9maWwgcHJvIFVzZXIgaW1wbGVtZW50aWVyZW4sIGluZGVtIEVtcGZlaGx1bmdlbiB1bmQgTnV0emVycHJvZmlsIGltIDE5IGRpbWVuc2lvbmFsZW4gR2VucmUgUmF1bSB2ZXJnbGljaGVuIHdlcmRlbi4gRGllIEZ1bmt0aW9uIGNyZWF0ZV9jbGV2ZWxhbmRfcGxvdCgpIHZlcndlbmRldCBpZGVhbGVyd2Vpc2UgZGllIEZ1bmt0aW9uIGdldF90b3BuX3JlY29zKCkNCg0KSW1wbGVtZW50IGNyZWF0ZV9jbGV2ZWxhbmRfcGxvdCgpIGZ1bmN0aW9uIHRvIHZpc3VhbGx5IGNvbXBhcmUgdG9wIE4gcmVjb21tZW5kYXRpb25zIGFuZCB1c2VyIHByb2ZpbGUgcGVyIHVzZXIgYnkgY29tcGFyaW5nIHJlY29tbWVuZGF0aW9ucyBhbmQgdXNlciBwcm9maWxlIGluIDE5IGRpbWVuc2lvbmFsIGdlbnJlIHNwYWNlLiBUaGUgY3JlYXRlX2NsZXZlbGFuZF9wbG90KCkgZnVuY3Rpb24gaWRlYWxseSB1c2VzIHRoZSBnZXRfdG9wbl9yZWNvcygpIGZ1bmN0aW9uDQoNCmBgYHtyfQ0KDQpjcmVhdGVfY2xldmVybGFuZF9wbG90IDwtIGZ1bmN0aW9uKG14LGksbil7ICAjIG14OmlucHV0IGRhdGE7IGk6IHRoZSBpdGggdXNlcjsgbjogbnVtYmVyIG9mIHRvcC1OIHJlY29tbWVuZGVyDQogICMgdG9wLU4gcmVjb21tZW5kYXRpb24gbGlzdHMNCiAgdG9wX24gPC0gYXMuZGF0YS5mcmFtZSh0KGdldF90b3BuX3JvY29zKG14W2ksXSxuKSkpICU+JSBzbGljZSgyOihuKzEpKSANCiAgZGZfbW92aWVfZ2VucmUgPC0gYXMuZGF0YS5mcmFtZShteF9tb3ZpZV9nZW5yZSkgDQogIG5yX2dlbnJlIDwtIGRpbShteF9tb3ZpZV9nZW5yZSlbMl0NCiAgZGZfbW92aWVfZ2VucmUkbW92aWVfbmFtZSA8LSByb3duYW1lcyhkZl9tb3ZpZV9nZW5yZSkNCiAgdG9wX25fbW92aWVfZ2VucmUgPC0gbGVmdF9qb2luKHRvcF9uLGRmX21vdmllX2dlbnJlLGJ5PWMoIlYxIj0ibW92aWVfbmFtZSIpKSU+JXNlbGVjdCgtVjEpDQogIHRvcF9uX21vdmllX2dlbnJlIDwtIGNvbFN1bXModG9wX25fbW92aWVfZ2VucmUsbmEucm09VFJVRSxkaW1zPTEpDQogIA0KICAjIHVzZXIgcHJvZmlsZQ0KICByYiA8LSByYmluZCh0b3Bfbl9tb3ZpZV9nZW5yZSxteF91c2VyX2dlbnJlW2ksXSkNCiAgcm93bmFtZXMocmIpIDwtIGMoIlRvcF9uIiwidXNlcl9wcm9maWxlIikgDQogIHJiIDwtIGFzLmRhdGEuZnJhbWUodChyYikpICU+JSBhcnJhbmdlKGRlc2MoVG9wX24pKQ0KICByYiRnZW5yZSA8LSByb3duYW1lcyhyYikgDQogIHJiLmxvbmcgPC0gcGl2b3RfbG9uZ2VyKHJiLGNvbHM9YyhUb3Bfbix1c2VyX3Byb2ZpbGUpLG5hbWVzX3RvPSJ0eXBlIix2YWx1ZXNfdG89ImNvdW50IikgJT4lIGFycmFuZ2UoZGVzYyhjb3VudCkpDQoNCiAgYyA8LSBnZ3Bsb3QocmIubG9uZywgYWVzKGNvdW50LCBmY3RfaW5vcmRlcihnZW5yZSkpKSArDQogICAgICAgIGdlb21fbGluZShhZXMoZ3JvdXAgPSBnZW5yZSkpICsNCiAgICAgICAgZ2VvbV9wb2ludChhZXMoY29sb3IgPSB0eXBlKSkgKyANCiAgICAgICAgbGFicyh4PSJjb3VudCIsIHk9ImdlbnJlIix0aXRsZT0gcGFzdGUoIlVzZXIgIixpLCI6IFRvcCAtICIsIG4sICIgcmVjb21tZW5kYXRpb25zIFZTIHVzZXIgcHJvZmlsZSAiKSApKyANCiAgICAgICAgdGhlbWUocGxvdC50aXRsZSA9IGVsZW1lbnRfdGV4dChoanVzdCA9IDAuNSkpIA0KICByZXR1cm4oYykNCn0NCg0KDQpwYXIobWZyb3c9YygyLDIpKQ0KY3JlYXRlX2NsZXZlcmxhbmRfcGxvdChteF9yYXRpbmdzX2FsbF9tb3ZpZSw1LDIwKQ0KY3JlYXRlX2NsZXZlcmxhbmRfcGxvdChteF9yYXRpbmdzX2FsbF9tb3ZpZSwyNSwyMCkNCmNyZWF0ZV9jbGV2ZXJsYW5kX3Bsb3QobXhfcmF0aW5nc19hbGxfbW92aWUsNTAsMjApDQpjcmVhdGVfY2xldmVybGFuZF9wbG90KG14X3JhdGluZ3NfYWxsX21vdmllLDE1MCwyMCkNCg0KYGBgDQojIyMgVGhlIFRvcC0yMCByZWNvbW1lbmRhdGlvbnMgc2hvdyB2ZXJ5IHNpbWlsaWFyIHRyZW5kIGFzIHRoZSB1c2VyIHByb2ZpbGUuICAgICAgICANCg0KDQo0LjcgRsO8ciBOdXR6ZXIg4oCcMTMz4oCdIHVuZCDigJw1NTXigJ0gUHJvZmlsIG1pdCBUb3AtTiBFbXBmZWhsdW5nZW4gZsO8ciBOID0gMjAsIDMwLCA0MCwgNTAgYW5hbHlzaWVyZW4sIHZpc3VhbGlzaWVyZW4gdW5kIGRpc2t1dGllcmVuLg0KDQpgYGB7cn0NCnBhcihtZnJvdz1jKDQsMikpDQpjcmVhdGVfY2xldmVybGFuZF9wbG90KG14X3JhdGluZ3NfYWxsX21vdmllLDEzMywyMCkNCmNyZWF0ZV9jbGV2ZXJsYW5kX3Bsb3QobXhfcmF0aW5nc19hbGxfbW92aWUsMTMzLDMwKQ0KY3JlYXRlX2NsZXZlcmxhbmRfcGxvdChteF9yYXRpbmdzX2FsbF9tb3ZpZSwxMzMsNDApDQpjcmVhdGVfY2xldmVybGFuZF9wbG90KG14X3JhdGluZ3NfYWxsX21vdmllLDEzMyw1MCkNCmNyZWF0ZV9jbGV2ZXJsYW5kX3Bsb3QobXhfcmF0aW5nc19hbGxfbW92aWUsNTU1LDIwKQ0KY3JlYXRlX2NsZXZlcmxhbmRfcGxvdChteF9yYXRpbmdzX2FsbF9tb3ZpZSw1NTUsMzApDQpjcmVhdGVfY2xldmVybGFuZF9wbG90KG14X3JhdGluZ3NfYWxsX21vdmllLDU1NSw0MCkNCmNyZWF0ZV9jbGV2ZXJsYW5kX3Bsb3QobXhfcmF0aW5nc19hbGxfbW92aWUsNTU1LDUwKQ0KYGBgDQoNCiMjIyBJbiB0aGUgdHdvIHVzZXIgZXhhbXBsZXMsIHRoZSB1c2VyIDU1NSBoYXMgcmF0ZWQgbW9yZSBmaWxtcyB0aGFuIHVzZXIgMTMzLiBDb21wYXJpbmcgdG8gdGhlIHVzZXIgMTMzLCB0aGUgdG9wLW4gcmVjb21tZW5kYXRpb24gZm9yIHVzZXIgNTU1IHNob3dlZCBub3Qgb25seSBzaW1pbGlhciB0cmVuZCB0byB0aGUgdXNlciBwcm9maWxlLCBidXQgYWxzbyBzdGFibGUgcGVyZm9ybWFuY2Ugd2l0aCBkaWZmZXJlbnQgbiBzZXR0aW5ncyAoTiA9IDIwLDMwLDQwLDUwKS4gVGhpcyBtZWFucywgdGhlIHVzZXJzIHdobyBoYXMgcmF0ZWQgbW9yZSBmaWxtcyB3aWxsIGdldCBtb3JlIGlkZWFsIHJlY29tbWVuZGF0aW9ucy4gDQoNCg==